The Location Design and Routing problem asks one to find a subset of “depot” nodes and a spanning forest of a graph such that every connected component in the forest contains at least one depot. See G. Laporte, “Location-routing problems,” in Vehicle Routing: Methods and Studies, B. L. Golden, and A. A. Assad, Eds. Elsevier, 1988, pp. 163-197. A typical scenario takes the form of creating an optimal distribution network. Given a network of roads, how many distribution centers need be built—and in which locations—such that deliveries can be carried out as quickly as possible? What if the cost of building distribution centers is nonuniform with respect to location? Scenarios are not strictly limited to logistical domains; in computer networking and multiagent systems, for example, the unavailability of a central server/database necessitates data redundancy in the system. See M. Peysakhov, R. N. Lass, W. C. Regli, and M. Kam, “An ecological approach to agent population management,” in Proceedings of the Twentieth National Conference on Artificial Intelligence, 2005, pp. 146-151. Many peer-to-peer systems, such as service oriented architectures and distributed hash tables, promote certain nodes to be supernodes. In this setting, the supernodes are akin to the depots in the location design and routing problem. The problem of selecting which subset of peers should perform a certain role such that they are well dispersed in the network—what is referred to as the supernode selection problem (V. Lo, D. Zhou, Y. Liu, C. Gauthier-Dickey, and J. Li, “Scalable supernode selection in peer-to-peer overlay networks,” in Proceedings of the Second International Workshop on Hot Topics in Peer-to-Peer Systems, Washington, D.C., USA: IEEE Computer Society, 2005, pp. 18-27) is therefore equivalent to the location design and routing problem. Such problems also appear in the fields of sensor networks and peer-based grid computing.
FIG. 1 provides an example of a weighted distribution network (FIG. 1(a)), along with two optimal solutions, FIGS. 1(b) and 1(c), depending on the cost of opening a depot. In general, finding a set of depots and a spanning forest of minimal weight is NP-Hard (J. Melechovský, C. Prins, and R. W. Calvo, “A metaheuristic to solve a location-routing problem with non-linear costs,” Journal of Heuristics, vol. 11, no. 5-6, pp. 375-391, 2005).
The sequential variant of the Location Design and Routing problem has been thoroughly studied in the literature (See, e.g., M. X. Goemans and D. P. Williamson, “A general approximation technique for constrained forest problems,” SIAM Journal on Computing, vol. 24, pp. 296-317, 1995), culminating in the discovery that the problem submits to bounded approximation in polynomial time. There are, therefore, three primary motivations for developing a distributed approximated solution to the problem:
1. The problem itself is naturally distributed—there may not be an obvious central node in which to perform the desirable optimizations;
2. Local properties of the underlying networks seem to allow for speedups from distributed processing; and
3. In certain environments, such as sensor networks, hardware restrictions might necessitate decentralization in order to save memory and computational resources.
Although there is very little in the literature on the parallelization and distribution of this specific problem, the related problem of finding a minimum spanning forest has been widely studied and are known to be soluble in logarithmic time with a linear number of processors. (See S. Halperin and U. Zwick, “Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems,” in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, Pa., USA: Society for Industrial and Applied Mathematics, 1996, pp. 438-447, and R. Cole, P. N. Klein, and R. E. Tarjan, “Finding minimum spanning forests in logarithmic time and linear work using random sampling,” in Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, New York, N.Y., USA: ACM, 1996, pp. 243-250.) In fact, finding a minimum spanning forest is a special case of the location design and routing problem in which depot opening costs are very large (i.e., greater than the diameter of the graph). To the best of the inventors' knowledge, however, the converse is not true: There is no known trivial reduction from the location design and routing problem to the spanning forest problem.
Proposing distributed algorithms using the primal/dual schema has also been the subject of study of a number of recent results. See A. Panconesi, Fast Distributed Algorithms Via Primal-Dual (Extended Abstract), Heidelberg: Springer, 2007, vol. 4474/2007, pp. 1-6. Problems that have been studied using this schema include Steiner problems (M. Santos, L. M. A. Drummond, and E. Uchoa, A Distributed Primal-Dual Heuristic for Steiner Problems in Networks, Springer, 2007, vol. 4525/2007, pp. 175-188), point-to-point connectivity problems (R. C. Corrêa, F. C. Gomes, C. A. S. Oliveira, and P. M. Pardalos, “A parallel implementation of an asynchronous team to the point-to-point connection problem,” Parallel Computing, vol. 29, no. 4, pp. 447-466, 05/2002 2002), distributed scheduling (A. Panconesi and M. Sozio, “Fast distributed scheduling via primal-dual,” in Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, ACM. Munich, Germany: ACM, 2008, pp. 229-235), vertex cover (S. Khuller, U. Vishkin, and N. Young, “A primal-dual parallel approximation technique applied to weighted set and vertex cover,” Journal of Algorithms, vol. 17, no. 2, pp. 280-289, October 1994; and F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio, “Primal-dual based distributed algorithms for vertex cover with semi-hard capacities,” in Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, Las Vegas, Nev., USA, 2005, pp. 118-125), and facility location (M. Sozio, “Efficient distributed algorithms via the primal-dual schema,” Ph. D. Dissertation, “La Sapienza” University, Rome, September 2006). Control theoretic approaches have also been used to solve stochastic variants of the vehicle routing problem (E. Frazzoli and F. Bullo, “Decentralized algorithms for vehicle routing in a stochastic time-varying environment,” in Proceedings of the 43rd IEEE Conference on Decision and Control, vol. 4, December 2004, pp. 3357-3363).
To the best of the inventors' knowledge, however, there is no prior result which theoretically proves a constant bound on the cost of the optimal solution and provides a poly-logarithmic bound on the number of communication rounds for the optimization problem. Algorithms for addressing this problem, including a bounded distributed version of an approximation algorithm for the location design and routing problem that runs in a logarithmic number of communication rounds with respect to the number of nodes, is desired and will be described herein.